Software programs have been written to run sequentially since the beginning days of software development. Steadily over time computers have become much more powerful, with more processing power and memory to handle advanced operations. This trend has recently shifted away from ever-increasing single-processor clock rates and towards an increase in the number of processors available in a single computer, i.e. away from sequential execution and toward parallel execution. Software developers want to take advantage of improvements in computer processing power, enabling their software programs to run faster as new hardware is adopted. With parallel hardware, however, this requires a different approach: developers must arrange for one or more tasks of a particular software program to be executed in parallel (sometimes called “concurrently”), so that the same logical operation can utilize many processors at one time, and deliver better performance as more processors are added to the computers on which such software runs.
When parallelizing previously-written sequential algorithms, it is often desirable to keep as much of the previous sequential program behavior as is possible. However, typical parallel execution of existing sequential logic introduces new behavioral characteristics and presents problems that can introduce challenges into the migration from sequential to parallel algorithms. Moreover, it is also possible that such a problem could represent changes to non-negotiable sequential behavior, prohibiting migration altogether. One category of such problems is that of preserving data ordering, either by ordinal position or keys generated based on programmer specified key-selection logic.
As an illustration, imagine a programmer wrote this program text, which uses a language integrated query comprehension as a way of representing a data parallel computation:
int[ ] A = ... generate some interesting input ...;Array.Sort(A); // sort ‘A’ in placeint[ ] B = (from x in A select x*x).ToArray( );
The sequential algorithm preserves relative ordering among elements in ‘A’ for the output elements in ‘B’, simply by virtue of the sequential evaluation of the query whose results are assigned to ‘B’. If the query comprehension is run in parallel using typical data parallel execution, the relative ordering among elements may become scrambled. As an example, imagine ‘A’ contains the elements {0, 1, 2, 3}; the programmer will likely expect that, after execution, ‘B’ contains {0, 1, 4, 9}. This problem can apply generally to all data parallel operations, not just query comprehensions.